package 回溯;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/target-sum/
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493615&idx=1&sn=5a06ed930c37e1a1d6ebfde76084ff3e&chksm=9bd419e7aca390f1c32e3f2a9827eb0e7e0fa0975ee5e3b5a7505427c347ca2699a7ecf744c2&scene=178&cur_album_id=2165135739779448832#rd
 */
public class _494_目标和 {

    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, target);
    }

    private Map<String, Integer> meno = new HashMap<>();

    private int dfs(int[] nums, int i, int rest) {
        if (i == nums.length) {
            if (rest == 0) return 1;
            return 0;
        }

        // 转成字符串才能作为哈希表的键盘
        String key = i + "," + rest;
        // 避免重复计算
        Integer result = meno.get(key);
        if (result == null) {
            // 还是穷举
            result = dfs(nums, i + 1, rest + nums[i]) + dfs(nums, i + 1, rest - nums[i]);
            // 记录到备忘录
            meno.put(key, result);
        }
        return result;
    }
}

